package Top200;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @author zhangmin
 * @create 2022-02-18 11:25
 * 回溯
 */
public class letterCombinations17 {
    Map<Character,Character[]> map=new HashMap<>();
    List<String > res=new LinkedList<>();
    void backtrack(String digits,int index,StringBuffer path){
        if (index==digits.length()){
            res.add(path.toString());
            return;
        }
        char c = digits.charAt(index);
        Character[] characters = map.get(c);
        for (Character cc:characters) {
            path.append(cc);
            backtrack(digits,index+1,path);
            path.deleteCharAt(index);
        }
    }
    public List<String> letterCombinations(String digits) {
        if (digits.length()==0) return res;
        map.put('2',new Character[]{'a','b','c'});
        map.put('3',new Character[]{'d','e','f'});
        map.put('4',new Character[]{'g','h','i'});
        map.put('5',new Character[]{'j','k','l'});
        map.put('6',new Character[]{'m','n','o'});
        map.put('7',new Character[]{'p','q','r','s'});
        map.put('8',new Character[]{'t','u','v'});
        map.put('9',new Character[]{'w','x','y','z'});
        backtrack(digits,0,new StringBuffer());
        return res;
    }
}
